package com.sourcetrip.algorithm.sort.bubble;

import com.sourcetrip.algorithm.abs.AbstractSort;

/**
 * @author: xiaomi
 * @date: 2020/12/27
 * @description: 冒泡排序的优化 V2
 * 分析：
 * 针对尾部存在有序的情况 ——>记录上一次交换的位置，而不是一直到 end 的位置进行比较；
 * 反思：
 * 但是这种情况也只针对原始数组尾部部分有序的情况。所以概率也不是很高。
 * 其实错了，当中间部分的交换也能达到尾部有序的情况时，也是优化，所以概率可观！
 */
public class BubbleSortV2 extends AbstractSort {


    /**
     * 写排序感觉最需要留意索引的边界！需要特别留意！
     * 不然即使思路对了，答案也会很有很大的偏差，甚至怀疑自己的思路！
     * @param arr
     * @return
     */
    @Override
    protected int[] sortArr(int[] arr) {
        boolean swaped = false;
        for (int end = arr.length - 1, lastIndex = 0; end > 0; end--) {
            swaped = false;
            for (int i = 1; i <= end; i++) {
                if (arr[i - 1] > arr[i]) {
                    swap(arr, i - 1, i);
                    lastIndex = i;
                    swaped = true;
                }
            }
            if (swaped) {
                end = lastIndex;
            }
        }
        return arr;
    }


    /**
     * 这是我的有异常的写法
     * because:当数组完全有序时，依然走 V0的老路。
     *
     * @param arr
     * @return
     */
    int[] myErrorMethod(int[] arr) {

        for (int i = arr.length, lastIndex = i, end = lastIndex; i > 0; i--) {
            end = lastIndex;
            for (int j = 1; j < end; j++) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                    lastIndex = j;
                }
            }
        }
        return arr;
    }

    /**
     * 这是修复之后的版本，但是由于存在变量优化的空间，以及多余的判断，所以又写了一遍
     *
     * @param arr
     * @return
     */
    int[] myFixedMethod(int[] arr) {
        for (int i = arr.length, end = i, lastIndex = 0; i > 0; i--) {
            //当全部有序时，不会处理交换，此时 lastIndex 的作用就出来了！
            for (int j = 1; j < end; j++) {
                if (arr[j - 1] > arr[j]) {
                    swap(arr, j - 1, j);
                    lastIndex = j;
                }
            }
            end = lastIndex;
            //由于 1<end 不成立时，就不需要一直执行外循环，所以这里加一个判断
            if (end < 1) {
                break;
            }
        }
        return arr;
    }
}
